// 152.乘积最大子数组
package Leetcode_Second_Brush;

public class Solution152 {
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int[] dpMax = new int[length];
        int[] dpMin = new int[length];

        dpMax[0] = nums[0];
        dpMin[0] = nums[0];

        int result = dpMax[0];

        for (int i = 1; i < nums.length; i++) {
            int max = dpMax[i - 1];
            int min = dpMin[i - 1];

            dpMax[i] = Math.max(Math.max(nums[i], nums[i] * max), nums[i] * min);
            dpMin[i] = Math.min(Math.min(nums[i], nums[i] * max), nums[i] * min);

            result = Math.max(result, dpMax[i]);
        }

        return result;
    }
}
